package sort;

import java.util.Arrays;

/**
 * @author RunningShrimp
 * @date 2021/6/16  13:54
 * @see <a href=""></a>
 */
public class HeapSort<E extends Comparable<E>> extends BaseSort<E> {
    @Override
    public void sort(E[] array) {

        int length = array.length;

        buildMaxHeap(array, length);

        for (int i = length - 1; i > 0; i--) {
            exchange(array, 0, i);
            length--;
            heapify(array, 0, length);
        }
    }

    private void heapify(E[] array, int i, int length) {
        System.out.println("堆化前的数组" + Arrays.toString(array));
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < length && less(array[left], array[largest])) {
            largest = left;
        }

        if (right < length && less(array[right], array[largest])) {
            largest = right;
        }
        if (largest != i) {
            exchange(array, i, largest);
            heapify(array, largest, length);
        }
        System.out.println("堆化后的数组" + Arrays.toString(array));
        System.out.println();
    }

    private void buildMaxHeap(E[] array, int length) {
        for (int i = (int) Math.floor(length * 1.0 / 2); i >= 0; i--) {
            heapify(array, i, length);
        }
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[]{10, 8, 9, 2, 5};
        BaseSort<Integer> sort = new HeapSort<>();

//        System.out.println("排序前：");
//        sort.show(array);
        sort.sort(array);
//        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
    }
}
